package cuiyt.algorithm.dfs;

import org.junit.Test;

import java.util.ArrayList;
import java.util.Arrays;

/**
 * @author cyt
 * @create 2020-09-02 9:56
 */
public class T1619 {

    /**
     * 你有一个用于表示一片土地的整数矩阵land，该矩阵中每个点的值代表对应地点的海拔高度。若值为0则表示水域。
     * <p>
     * 由垂直、水平或对角连接的水域为池塘。池塘的大小是指相连接的水域的个数。编写一个方法来计算矩阵中所有池塘的大小，返回值需要从小到大排序。
     * 输入：
     * [
     * [0,2,1,0],
     * [0,1,0,1],
     * [1,1,0,1],
     * [0,1,0,1]
     * ]
     * 输出： [1,2,4]
     *
     * @param args
     */
    public static void main(String[] args) {
    }


    ArrayList<Integer> ans = new ArrayList<>();
    int[][] dirs = {
            {-1, 0}, {1, 0}, {0, -1}, {0, 1},
            {-1, -1}, {-1, 1}, {1, -1}, {1, 1}
    };


    @Test
    public void pondSizes() {

        int[][] land = new int[][]{
                {0, 2, 1, 0},
                {0, 1, 0, 1},
                {1, 1, 0, 1},
                {0, 1, 0, 1}
        };
        for (int i = 0; i < land.length; i++) {
            for (int j = 0; j < land[0].length; j++) {
                if (land[i][j] == 0) {
                    /**
                     * 可以开始搜索
                     */
                    System.out.println(i + " - > " + j);
                    ans.add(dfs(i, j, land));
                }
            }
        }
        int[] ints = new int[ans.size()];
        for (int i = 0; i < ans.size(); i++) {
            ints[i] = ans.get(i);
        }
        Arrays.sort(ints);
        for (int anInt : ints) {
            System.out.println(anInt);
        }
    }

    public int dfs(int x, int y, int[][] land) {
        int cnt = 1;
        land[x][y] = -1;
        for (int[] dir : dirs) {
            int newI = x + dir[0];
            int newJ = y + dir[1];
            if (0 <= newI && newI < land.length && 0 <= newJ && newJ < land[0].length && land[newI][newJ] == 0) {
                cnt += dfs(newI, newJ, land);
            }
        }
        return cnt;
    }
}
